/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-09 15:11:13
 * @LastEditors: lily
 * @LastEditTime: 2021-04-12 14:41:09
 */
/*
 * @lc app=leetcode.cn id=32 lang=javascript
 *
 * [32] 最长有效括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */

//  思路：
//  1) 栈 利用额外数组记录当前index是否有效 最后找出最长有效的字串
//  2) 动态规划 找出内部、外部、当前有多少有效的括号，根据前一个index计算状态转移方程

//  复杂度：O(n) O(n)

var longestValidParentheses = function (s) {
    // 法一：栈
    // 记录有效括号的长度
    const valid = Array(s.length).fill(0)
    const stack = []

    for (let i = 0; i < s.length; i++) {
        //  左括号入栈
        if (s[i] === '(') stack.push(i)
        // 右括号且栈不为空
        if (s[i] === ')' && stack.length > 0) {
            // 当前右括号的索引设为有效
            valid[i] = 1;
            // 当前右括号匹配的左括号的索引设为有效
            valid[stack.pop()] = 1
        }
    }

    // 找出最长的1
    let count = 0, max = 0
    for (let v of valid) {
        v && count++
        v || (count = 0)
        count > max && (max = count)
    }
    return max


    // 法二：动态规划
    /* 
        // 状态：以当前字符结尾的字符串，最长的有效括号长度是多大
        const dp = Array(s.length).fill(0);
    
        for (let i = 1; i < s.length; i++) {
            // 有效括号只能是以 ')' 结尾的
            // 所以，以 '(' 结尾的字符串，最长有效括号长度就是 0，不用管
            if (s[i] === ')') {
                // 遇到 ')' 时，往左边去找跟它匹配的 '('，如果存在，那么有效长度在 dp[i - 1] 基础上加 2
                // dp[i - 1] 是以 s[i - 1] 结尾的字符串的最长有效括号长度，设它为 k，
                // 也就是 [i - k, i - 1] 这段是有效括号字符串，
                // 如果这段字符串前面的那个字符 s[i - k - 1] 是 '(' 的话，那么有效长度加 2
                if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
                    dp[i] = dp[i - 1] + 2;
    
                    // 如果匹配到的 '(' 前面还有有效长度的话，也加上
                    if (i - dp[i - 1] - 2 > 0) {
                        dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
        }
        return Math.max(...dp, 0);
    */
};
// @lc code=end

console.log(longestValidParentheses("()(()())"));